﻿namespace Leetcode.N0440;
public class Solution
{
    public int FindKthNumber(int n, int k)
    {
        var rootValue = 1;
        k--;

        while (k > 0)
        {
            var count = this.GetCount(n, rootValue);
            if (count <= k)
            {
                rootValue++;
                k -= count;
            }
            else
            {
                rootValue *= 10;
                k--;
            }
        }
        return rootValue;
    }

    public int GetCount(int num, int rootValue)
    {

        long minValue = rootValue;
        long maxValue = rootValue;
        long count = 0;
        while (minValue <= num)
        {
            count += Math.Min(num, maxValue) - minValue + 1;
            minValue = minValue * 10;
            maxValue = maxValue * 10 + 9;
        }
        return (int)count;
    }
}
